package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;
/**
 * 日期：2023/10/17
 * 时间：8:53
 * 描述：二叉树删除
 * @author songj
 */
public class E04Lettcode450 {
    public TreeNode deleteNode(TreeNode<Integer> root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }

        //到这里就是找到了
        if (root.left == null && root.right == null) {
            return null;
        }

        if (root.right == null) {
            return root.left;
        }
        if (root.left == null) {
            return root.right;
        }
//        寻找后继节点
        TreeNode treeNode = root.right;
        while (treeNode.left != null) {
            treeNode = treeNode.left;
        }
        treeNode.right = deleteNode((TreeNode<Integer>) root.right, (Integer) treeNode.val);
        treeNode.left = root.left;
        return treeNode;
    }
}

